Programmation fonctionnelle - TD 3 : Arbres lexicographiques

Un arbre lexicographique (ou “trie”) est une structure utilisée pour représenter des ensembles dont les éléments admettent une décomposition séquentielle en “caractères” possédant de plus un ordre (par exemple, les entiers admettent une décomposition en suite de chiffres, les chaînes de caractères en suite de caractères, etc).

Un arbre lexicograhique contient :

• une fonction de décomposition permettant de transformer un élément en liste de “caractères”
• une fonction de recomposition, inverse de la procédure
• un arbre n-aire dont les branches représentent les suites constituant les éléments stockés dans l’ensemble, les “caractères” étant rangés dans les branches

De plus, les branches sont triées de gauche à droite. Pour chaque noeud, il doit être indiqué si la suite lue depuis la racine constitue la décomposition d’un élément ou seulement un préfixe strict d’une telle décomposition.

Il vous est demandé de ranger les “caractères” dans les branches. Un exemple d’arbre lexicographique stockant le long des branches les mots du mini-dictionnaire suivant : bas, bât, de, la, lai, laid, lait, lard, le, les, long est présenté sur la figure suivante :

1. Structure arborescente n-aire

Dans un premier temps, nous nous intéresserons juste à la structure arborescnete n-aire.

Exercice 1 (Définition des types) : Définir le type 'a arbre représentant la structure arborescente : arbre n-aire avec les booléens dans les noeuds et des 'a dans les branches. Vous pouvez également définir un second type représentant les branches.

type 'a arbre = Noeud of bool * ('a * 'a arbre) list

(* Solution du cours : *)
type 'a branche = 'a * 'a arbre 
and 'a arbre = Noeud of bool * 'a branche list

(* Définition de l'arbre exemple *)
let bb = (b, Noeud(false, [...]) 
let bd = (d, Noeud(false, [...])
let bl = (b, Noeud(false, [...])
let b1 = [bb;bd;bl]
let arbre_sujet = Noeud(false,b1)

Exercice 2 (Test d’appartenance) : Ecrire la fonction appartient qui teste si un élément appartient bien à un ensemble représenté par un arbre lexicographique.

(* Contrat
recherche : 'a -> ('a * 'b) list -> 'b option - Retourne une branche
commançant par un caractère donné s'il en exite une.
Paramètres :
    - c : 'a - caractère
    - lb : ('a * 'b) list - liste de branches
Résultat : 'b option - Branche qui commence par c si ça existe
*)
let rec recherche c lb =
    match lb with
    | [] -> None
    | (carock,abr)::q -> 
        if carock > c then 
            None
        else
            if carock = c then 
                Some abr
            else
                recherche c q


(* Contrat
appartient : 'a list -> 'a arbre -> bool - Retourne si un élément 
    est dans un ensemble représenté par un arbre lexicographique
Paramètres :
    - m : 'a list - élément à rechercher
    - abr : 'a arbre - arbre lexicographique
Résultat : bool - Vrai si x est dans abr, faux sinon
*)
let rec appartient m (Noeud(b,l)) = 
    match m with 
    | [] -> b
    | t::q -> 
        match recherche t l with
        | None -> false
        | Some(x) -> appartient q x 

Exercice 3 (Ajout) : Ecrire la fonction ajout qui ajoute un élément à un ensemble représenté par un arbre lexicographique.

(* Contrat
maj : 'a -> 'b -> ('a * 'b) list -> ('a * 'b) list -
    Met à jour une branche avec un caractère donné dans la liste de branches
    avec la nouvelle branche donnée. 
Paramètres :
    - c : 'a - caractère
    - b : 'b - la branche
    - lb : ('a * 'b) list - la liste des branches
Résultat : ('a * 'b) list - la liste des branches avec la branche mise à jour
*)
let rec maj c b lb =
    match lb with
    | [] -> [c,b]
    | (tc,ta)::q ->
        if c < tc then
            (c,b)::lb
        else
            if c = tc then
                (c,b)::q
            else
                (tc,ta)::(maj c b q)

(* Contrat
ajout : 'a list -> 'a arbre -> 'a arbre - 
    Ajoute un élément dans un arbre lexicographique
Paramètres : 
    - m : 'a list - élément à ajouter à l'arbre
    - abr : 'a arbre - arbre lexicographique
Résultat : 'a arbre - arbre où m a été ajouté à abr
*)
let rec ajout m (Noeud(b,lb)) = 
    match m with 
    | [] -> Noeud(true,lb)
    | c::q -> 
        let arbrec = 
            match recherche c lb with
            | None -> Noeud(false, [])
            | Some branche -> branche
        in Noeud(b, maj c (ajout q arbrec) lb)

2. Arbres lexicographiques

En plus de la structure arborescente, un arbre lexicographique contient une fonction de décomposition et une fonction de recomposition.
Par exemple, dans le cas d’un dictionnaire de mot, la fonction de décomposition sera de type string -> char list et la fonction de recomposition de type char list -> string, permettant par exemple de passer de "laid" à ['l';'a';'i';'d'].

Exercice 4 : Définir le type ('a,'b) trie permettant de représenter des arbres lexicographiques (arbres + fonction de décomposition + fonction de recomposition).

type ('a,'b) trie = Trie of 'b arbre * ('a -> 'b list) * ('b list -> 'a)

(*
'a -> 'b list : fonction de décomposition
'b list -> 'a : fonction de recomposition
*)

Exercice 5 (Test d’appartenance) : Ecrire la fonction appartient_trie qui teste si un élément appartient bien à un ensemble représenté par un arbre lexicographique.

(* Contrat
appartient_trie : 'a -> ('a,'b) trie -> bool -
    Teste si un élément appartient à un ensemble représenté
    par un arbre lexicographique
Paramètres :
    - mot : 'a - élément cherché
    - Trie(a,fd,fr) - arbre lexicographique
Résultat : bool - Vrai si l'élément est dans l'arbre, faux sinon
*)
let appartient_trie mot Trie(a, fd, fr) = 
    let lmot = fd mot in appartient (fd lmot) a

Exercice 6 (Ajout) : Ecrire la fonction ajout_trie qui ajoute un élément à un ensemble repésenté par un arbre lexicographique.

(* Contrat
ajout_trie : 'a -> ('a,'b) trie -> ('a,'b) trie -
    Ajoute un élément à un ensemble représenté
    par un arbre lexicographique
Paramètres :
    - mot : 'a - élément à ajouter
    - Trie(a,fd,fr) : ('a,'b) trie - arbre lexicographique
Résultat : ('a,'b) trie - Arbre de départ où on a ajouté mot
*)
let ajout_trie mot Trie(a, fd, fr) = 
    let lmot = fd mot in Trie(ajout (fd lmot) a, fd, fr)